﻿using System;
using System.Collections.Generic;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.Utils.Backtracers;

namespace Algoritmia.Problems.ShortestPaths
{
    public interface IShortestPathsFinder<TNode,TResult> : IMinimumDistanceFinder<TNode,TResult>
    {
        IEnumerable<KeyValuePair<TNode,TNode>> SomeToSomeBackpointers(IDigraph<TNode> g, WeightingFunction<TNode,TResult> d,
                                                  IEnumerable<TNode> sources, IEnumerable<TNode> targets);
    }

    public static class ShortestPathFindersExtensions
    {

        public static IEnumerable<TNode> ShortestPath<TNode,TResult>( this IShortestPathsFinder<TNode,TResult> pf , IDigraph<TNode> g , 
            WeightingFunction<TNode,TResult> d, TNode source, TNode target,
            Func<IEnumerable<KeyValuePair<TNode,TNode>>,IBacktracer<TNode,TNode>> createBacktracer = null)
        {
            createBacktracer = createBacktracer ?? (backpointers => new Backtracer<TNode>(backpointers));
            var backtracer = createBacktracer(pf.SomeToSomeBackpointers(g, d, new[] {source}, new[] {target}));
            return backtracer.Backtrace(target);
        }

    }
}
